#include<iostream>
#include<vector>
#include<tr1/unordered_map>
using namespace std;
class Solution
{
    // 扔进去AC了他
public:

    void swap(int & left, int & right)
    {
    int temp = left;
    left = right;
    right = temp;
    }

    int _Quick(vector<int>& arr,int l,int r)
    {
    int cur = l+1;
    int pre=l;
    int base = arr[l];
    while(cur<r)
    {
        if(arr[cur] < base)
        {
            pre++;
            swap(arr[cur],arr[pre]);
        }
        cur++;
    }
    swap(arr[l],arr[pre]);
    return pre;

    };
    int QuickSort(vector<int>& arr ,int l ,int r)
    {
    if(l>=r)
       return 0;
    int mid= _Quick(arr,l,r);
    QuickSort(arr,l,mid);
    QuickSort(arr,mid+1,r);
    return 0;
    };


   void print(vector<int>& arr,int n)
   {
    for(int i=0;i<n;i++)
        cout<< arr[i]<<' ' ;
    cout<< endl;

    };

    vector< vector<int> > threeSum(vector<int>& nums)
    {
        int n = nums.size();
        vector< vector<int> > arr;
        if (n<3)
            return arr;
//        QuickSort(nums,0,n);
        //print(nums,n);
        sort(nums.begin(), nums.end());
        if (nums[0]>0)
           return arr;

        for(int i=0;i<n-2;i++)
        {
            int l = i+1;
            int r = n-1;

            while(l<r)
            {
                int sum = nums[i] + nums[l] +nums[r];
                if(sum==0)
                {

//                    vector<int> temp;
//                    temp.push_back(nums[i]);
//                    temp.push_back(nums[l]);
//                    temp.push_back(nums[r]);
//                    arr.push_back(temp); //c++98
                    arr.push_back({nums[i],nums[l],nums[r]}); //c++11
                    while (l<r && nums[l+1]==nums[l])
                        l++;
                    l++;
                    while (l<r && nums[r-1]==nums[r])
                        r--;
                    r--;
                }
                else if(sum>0)
                   r--;
                else
                   l++;
            }
            while(i<n-2 && nums[i]==nums[i+1])
                i++;

        };
        return arr;
    };

};


int main() {
    int a[] = {-1,0,1,2,-1,-4};
//    int k = 0;
    int n = sizeof(a)/sizeof(a[0]);
    vector<int> arr(a,a+n);
    vector< vector<int> > ar;;
    ar = Solution().threeSum(arr);

    for(int i=0;i < ar.size();i++)
        {
            for(int j=0;j< ar[0].size();j++)
                cout<<ar[i][j]<<" ";
            cout << endl;
        }
    cout<<endl;
    return 0;
}